# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        totalSum = 0
        stack = [root]
        while stack:
            node = stack.pop()
            totalSum += node.val
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)

        def dfs(node, totalSum, ans):
            if node is None:
                return 0
            leftVal = dfs(node.left, totalSum, ans)
            rightVal = dfs(node.right, totalSum, ans)
            val = node.val + leftVal + rightVal
            ans[0] = max(ans[0], (totalSum - val) * val)
            return val

        ans = [0]
        dfs(root, totalSum, ans)

        return ans[0] % (10**9 + 7)
